洛谷题解 CF1713A 【Traveling Salesman Problem】

发表于 | 阅读次数：
本文字数： 1.6k | 阅读时长 ≈ 1 分钟

题目大意

一个人站在原点，x轴与y轴上分布有几个箱子，人每次只能走一个单位（上/下/左/右），求经过所有箱子并回到原点的最少步数

思路

箱子都在坐标轴上，而我们又知道两点之间线段最短

所以显然最短路就是到达各个轴上离原点最远的箱子后再折返

刚好在轴上来回走两次

至于题目给的样例图片走法

只要将路径平移至坐标轴就是我上面说的，总步数是一样的

因此只需要找出两条坐标轴正负半轴上离原点最远的箱子坐标就好了

答案就是找出来的四个点离原点的距离总和*2

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int t,n,mp[110][2],maxw[2],maxh[2];

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        maxw[0]=0;
        maxw[1]=0;
        maxh[0]=0;
        maxh[1]=0;
        for(int a=1;a<=n;++a)
        {
            
            scanf("%d%d",&mp[a][0],&mp[a][1]);
            if(mp[a][0]==0)
            {
                if(mp[a][1]>=0)
                {
                    maxh[1]=max(maxh[1],mp[a][1]);//y轴正方向
                }
                else
                {
                    maxh[0]=max(abs(mp[a][1]),maxh[0]);//y轴负方向
                }
            }
            else
            {
                if(mp[a][1]==0)
                {
                    if(mp[a][0]>=0)
                    {
                        maxw[1]=max(maxw[1],mp[a][0]);//x轴正方向
                    }
                    else
                    {
                        maxw[0]=max(abs(mp[a][0]),maxw[0]);//x轴负方向
                    }
                }
            }
            
        }
        printf("%d\n",(maxw[0]+maxw[1]+maxh[0]+maxh[1])*2);
    }
    return 0;
}

题目详见:https://www.luogu.com.cn/problem/CF1713A